package arithmetic.demo17;


import java.util.*;


/**
 * 题目： 拓扑排序_课程表
 */
class Solution {
    public boolean canFinish(int sum, int[][] relate) {


        //    准备工作
       int[] hash = new int[sum];
       Map<Integer, List<Integer>> edges = new HashMap<>(); 
        Queue<Integer> queue = new LinkedList<>();

        // 建立图
        for(int i =0; i < relate.length; i++) {
            int key = relate[i][0], value = relate[i][1];
            // 观察是否包含 key
            if(!edges.containsKey(key)) {
                edges.put(key, new ArrayList<>());
            }

            // 加入value
            edges.get(key).add(value);

            // 添加该节点入度的个数
            hash[value]++;
        }

        // 将度为 0 的节点加入到 队列中
        for(int i =0; i< sum ; i++) {
            if(hash[i] == 0) {
                queue.add(i);
            }
        }

        // 拓扑排序
        // 开始调整所有度为 0  的节点
        while(!queue.isEmpty()) {
            // 先获取到当前度为 0 的节点
            int cur = queue.poll();
            
            // 遍历cur 出度的节点
            for(int num : edges.getOrDefault(cur, new ArrayList<>())) {
                hash[num]--;
                // 一旦有节点为 0 的继续加入队列
                if(hash[num] == 0) {
                    queue.add(num);
                }
            }

        }


        // 检查是否有度不为 1 的情况
        for(int i =0; i< sum ; i++) {
            if(hash[i] != 0) {
                return false;
            }
        }


        return true;
    }
}


/**
 * 题目： 拓扑排序_课程表(2)
 */

class Solution1 {
    public int[] findOrder(int n, int[][] prere) {
        // 准备工作
        int[] ret = new int[n];
        Queue<Integer> queue = new LinkedList<>();
        int[] hash = new int[n];
        List<List<Integer>> edges = new ArrayList<>();

        // 先给 edges new  上一个空间
        for(int i = 0; i < n ; i++) {
            edges.add(new ArrayList<>());
        }

        // 开始建图
        for(int i =0; i < prere.length; i++) {
            int key = prere[i][1] , value = prere[i][0];
            edges.get(key).add(value);
            hash[value]++;
        }

        // 将度为 1 的节点 加入到队列中
        for(int i = 0; i< n ; i++) {
            if(hash[i] == 0) {
                queue.add(i);
            }
        }

        int k = 0;

        // 进行拓扑排序
        while(!queue.isEmpty()) {

            // 出度
            int cur =  queue.poll();
            ret[k++] = cur;
            for(int num : edges.get(cur)) {
                hash[num]--;
                // 如果度为 1 就继续加入到队列中
                if(hash[num] == 0) {
                    queue.add(num);
                }
            }

        }


        // 判断是否成环
        for(int i = 0; i< n; i++) {
            if(hash[i] != 0) return new int[0];
        }


        return ret;

    }
}


/**
 * 题目: 拓扑排序_火星人词典
 */

class Solution2 {
    public String alienOrder(String[] words) {
        // 准备工作
        StringBuilder ret = new StringBuilder();
        int n = words.length;
        Map<Character, List<Character>> edges = new HashMap<>();
        int[] hash = new int[26];
        boolean[] via = new boolean[26];
        Queue<Character> queue = new LinkedList<>();

        // 对出现过的字符进行初始化
        for (int i = 0; i < n; i++) {
            char[] tmp = words[i].toCharArray();
            for (int j = 0; j < tmp.length; j++) {
                via[tmp[j] - 'a'] = true;
            }
        }

        // 开始建图
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                char[] prev = words[i].toCharArray();
                char[] cur = words[k].toCharArray();
                int j = 0;
                // 寻找字符不相同的位置
                while (j < prev.length && j < cur.length && prev[j] == cur[j]) {
                    // 证明这个字符出现过
                    j++;
                }

                if(j < prev.length &&  j >= cur.length) return "";

                // 入度
                if (j < prev.length && j < cur.length) {
                    if (!edges.containsKey(prev[j])) {
                        edges.put(prev[j], new ArrayList<>());
                    }

                    if (!edges.get(prev[j]).contains(cur[j])) {
                        // 增加入度
                        edges.get(prev[j]).add(cur[j]);
                        // 统计度的个数
                        hash[cur[j] - 'a']++;
                    }

                }
            }

        }

        // 将度为 0 增加到队列中
        for (int i = 0; i < 26; i++) {
            if (hash[i] == 0 && via[i]) {
                queue.add((char) (i + 'a'));
            }
        }

        // 进行 拓扑排序
        while (!queue.isEmpty()) {
            // 出度
            char tmp = queue.poll();
            ret.append(tmp);

            for (char ch : edges.getOrDefault(tmp, new ArrayList<>())) {
                hash[ch - 'a']--;
                // 调整后重新入度
                if (hash[ch - 'a'] == 0) {
                    queue.add(ch);
                }
            }
        }

        // 检查是否有环
        for (int i = 0; i < 26; i++) {
            if (hash[i] != 0)
                return "";
        }

        return ret.toString();
    }
}


class Test {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        solution2.alienOrder(new String[]{"z","x"});
    }
}


/**
 * 题目: 贪心_柠檬水找零问题
 */


class Solution3 {
    public boolean lemonadeChange(int[] bills) {
        //  用来统计已有的零钱
        int five = 0, ten = 0, twenty = 0;

        for(int i = 0 ; i < bills.length ; i++) {
            if(bills[i] == 5) {
                five++;
            } else if(bills[i] == 10) {
                ten++;
                five--;
            } else {
                if(ten == 0) {
                    five -= 2;
                } else {
                    ten--;
                }
                five--;
                twenty++;
            }

            if(five < 0 || ten  < 0 || twenty < 0) return false;

        }



        return true;
    }
}


/**
 * 题目： 贪心_将数组和减半的最少操作次数
 */

class Solution4 {
    public int halveArray(int[] nums) {
        int ret = 0;
        // 建立一个大根堆
        PriorityQueue<Double> queue = new PriorityQueue<>((a,b)->{
            return  b.compareTo(a);
        });

        double sum = 0.0;
        // 将所有元素的加入到大根堆并统计总和
        for(int i =0; i< nums.length; i++) {
            queue.add((double)nums[i]);
            sum += nums[i];
        }

        double flg = sum / 2.0;
        while(sum > flg) {
            double num = queue.poll();
            sum -= (num / 2.0);
            queue.add(num / 2.0);
            ret++;
        }

        return ret;
    }
}